#include<iostream>
using namespace std;
class GraphNode {
public:
	char Data;
	int dex;
	GraphNode* next;
	GraphNode(char ch) {
		Data = ch;
		next = NULL;
	}
};
class Graph {
public:
	GraphNode** tmp;
	int N;
	Graph() {
		int n, k;
		cin >> n >> k;
		N = n;
		tmp = new GraphNode * [n];
		for (int i = 0; i < n; i++) {
			char ch;
			cin >> ch;
			tmp[i] = new GraphNode(ch);
			tmp[i]->dex = i;
		}
		for (int i = 0; i < k; i++){
			char ch1, ch2;
			cin >> ch1 >> ch2;
			for (int j = 0; j < n; j++) {
				if (tmp[j]->Data == ch1) {
					GraphNode* p = tmp[j];
					while (p->next != NULL) {
						p = p->next;
					}
					for (int k = 0; k < n; k++) {
						if (tmp[k]->Data == ch2) {
							p->next = new GraphNode(ch2);
							p->next->dex = k;
							break;
						}
					}
					break;
				}
			}
		}
	}
	void print() {
		for (int i = 0; i < N; i++) {
			GraphNode* p = tmp[i];
			cout << p->dex << ' ' << p->Data << '-';
			p = p->next;
			while (p != NULL) {
				cout << p->dex << '-';
				p=p->next;
			}
			cout << '^' << endl;
		}
	}
};
int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		Graph G;
		G.print();
	}
	return 0;
}